This application claims the benefit of U.S. Provisional Application No. 60/110,882, filed Dec. 4, 1998.
The present invention relates to a method and apparatus for efficient bit plane coding of transform coefficients, such as Discrete Cosine Transform (DCT) coefficients. Such coefficients may be used in a variety of applications, including digital video encoding and decoding. In particular, an improvement upon the technique known as Fine Granularity Scalability using Bit plane (FGSB) coding is presented.
FGSB coding keeps the base layer coding technique untouched. For example, the base layer coding technique can be MPEG-2, MPEG-4, or any DCT-based image/video coding technique. In the base layer, the DCT coefficients are coded using a relatively coarse quantization to obtain low bit rate data.
FIG. 1 illustrates a prior art apparatus for Fine Granularity Scalability using Bit plane (FGSB) coding. With FGSB coding, a difference (or residue) is obtained between the original integer DCT coefficients and dequantized DCT coefficients. As shown in the encoder 100, for example, an original block of DCT coefficients is quantized at a quantizer 110, then the quantized coefficients are dequantized (i.e., inverse quantized) at an inverse quantizer 120 to obtain the dequantized DCT coefficients. A difference block of DCT coefficients is output from a subtracter 130 and provided to a bit plane coding function 140 before being communicated across a channel. For example, the data may be communicated in a broadband communication network, such as a cable or satellite television network, or a computer network, such as a local area network (LAN), metropolitan area network (MAN), wide area network (WAN), internet, intranet, and the Internet. As mentioned, the base layer DCT coefficient data is coded conventionally.
The bit plane coding function 140 includes one or more tables 145 for coding the bits in each bit plane. The tables include an “all-zero” codeword that is used when a bit plane has all zero values.
Since each DCT difference block typically has a few bit planes (e.g., up to four to eight-planes in typical applications), fine granularity is achieved at very low complexity cost. The number of bit planes is determined by the number of bits needed to code the largest difference value. Essentially, DCT difference data in the successive bit plane layers can be used to reduce the DCT coefficient quantization error. One or more of the bit plane layers can be recovered by a decoder according to the available channel bandwidth and the decoder's processing speed. The bit plane layers are recovered starting from the layer carrying the most significant bit of the DCT difference data, then the layer carrying the next most significant bit of the DCT difference data, and so forth.
FGSB coding can be simplified into the following steps:
1. After performing base layer coding, which is DCT based, take the difference between the original DCT coefficients and the dequantized DCT coefficients. Find the number of bit planes required to code this difference block.
2. Find out the maximum number of bit planes from all the difference blocks of one video frame.
3. Code the maximum number of bit planes at the very beginning of one frame's enhancement layer bitstream.
4. Sequentially code the bit planes of one frame starting from the Most Significant Bit (MSB) level.
5. When coding a bit plane, 2-D symbols are formed of two components. The first component indicates the number of consecutive zeroes (e.g., zero run-length) until the next “1.”. The second component is a one-bit flag that indicates if there are any “1”s left in the current bit plane. The second component is therefore an End-Of-Plane (EOP) indicator. These 2-D symbols are then entropy coded. If there are no “1”s at all in the current bit plane, an “all-zero” symbol is coded.
The following illustrates an example of coding of a particular bit plane using the above approach, designated “prior art 1”.
Position:0123456. . .63bit value:10010100's0prior art 1, 2-D symbol(0,0)(2,0)(1,1)
In the first row, the “position” is the sequence of the bit in the bit plane. For example, for an 8×8 bit plane, there are 64 bits, e.g., 0–63. In the second row, the bit value is shown, either a binary 0 or 1.
In the third row, the 2-D symbols used by the prior art scheme discussed above are shown. Specifically, at position 0, the bit value is “1”, and the symbol is (0,0). The first component of the symbol, “0”, indicates that the run-length of zero symbols is 0 (i.e., there is no zero) before the next “1”. The second component of the symbol, “0”, which is the EOP indicator, indicates that there is at least one subsequent “1” in the bit plane. Note that the symbols are given in decimal numbers, which are later converted to binary (e.g., 210=102).
At position 1, the bit value is “0”, and the symbol is (2,0). The first component of the symbol, “2”, indicates that the run-length of zero symbols is 2 (i.e., there are zeroes in positions 1 and 2). Thus, the distance to the next “1” is 2 bit values (i.e., position 3). The second component of the symbol, “0”, again indicates that there are additional “1's” in the bit plane (i.e., in addition to the “1” in position 3).
At position 4, the bit value is “0”, and the symbol is (1,1). The first component of the symbol, “1”, indicates that the run-length of zero symbols is 1 (i.e., there is a zero in position 4). Thus, the distance to the next “1” is 1 bit value (i.e., position 5). The second component of the symbol, “1”, indicates that there are no additional “1's” in the bit plane (after position 5).
The above FGS coding method is discussed in ISO/IEC JTC1/SC29/WG11, MPEG98/M4204, December 1998, “Fine Granularity Scalability Using Bit plane Coding of DCT Coefficients.” With this technique, a bit plane with all zeroes is coded using the “all-zero” symbol, regardless of which bit plane layer is being coded. The all-zero symbol may need to be coded for more than one bit plane layer for a given DCT block. This is disadvantageous due to the size of the all-zero symbol, and the fact that it increases the coding table size.
In particular, the size (e.g., bit length) of the all-zero symbol is dictated by the entropy coding (e.g., Huffman coding) performed on the bit plane's 2-D symbols. As is known, when coding source symbols that are not equally probable, it is efficient to use variable-length code words. The probability of occurrence of the source symbols is used to select the code words so that more probable source symbols are assigned a shorter code word.
With these constraints, the length of the all-zero symbol is typically two bits or more. Furthermore, since there are several thousand 8×8 DCT blocks in an image (e.g., consider a 525×480 pixel NTSC image), the data overhead caused by the all-zero symbol is significant.
Accordingly, it would be desirable to provide a method and apparatus for efficient bit plane coding which improves over the above techniques. The system should reduce the number of bits required to indicate the presence of a bit plane in which all values are zero. The system should avoid the need for multiple “all-zero” symbols in the initial MSB bit plane layers of a single block having all zeroes, thereby reducing the data overhead for coding the bit plane.
The system should improve coding efficiency by reducing the number of symbols in a MSB level entropy coding table, thereby reducing the code length of the remaining symbols in the table.
The system should be compatible with coding schemes that provide multiple coding tables which are used for the different bit plane layers. Since the probability of occurrence of specific bits is different for the different bit plane layers, coding efficiency can be optimized by tailoring the coding table to the bit plane layer. This concept is discussed further in the Ph.D. dissertation entitled “Optimization of Entropy Coding Efficiency Under Complexity Constraints in Image and Video Compression,” (1998), Section 4.3, by Dr. Fan Ling, catalogued at the Electrical Engineering Department, Lehigh University, Pennsylvania, USA.
The present invention provides a system having the above and other advantages.